# -*- coding: utf-8 -*-

"""剑指 Offer II 053. 二叉搜索树中的中序后继
给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

示例 1：
输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：
输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示：
树中节点的数目在范围 [1, 104] 内。
-105 <= Node.val <= 105
树中各节点的值均保证唯一。"""

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """分两种情况：p 有右子树，则找到右子树中最小值
                  p 无右子树，则从根开始搜索，每次遇到大于 p.val 的节点都是其后面的节点，直到最近一个大于 p.val 的节点，便是 p 后继节点。（可以用反证法证明相继节点的就近关系）"""
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        if p.right:
            node = p.right
            while node.left:
                node = node.left
            return node

        after = None
        node = root
        while True:
            if p.val < node.val:
                after = node
                node = node.left
            elif p.val > node.val:
                node = node.right
            else:
                break
        return after

